/*
给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

 

示例 1:

输入: n = "123"
输出: "121"
示例 2:

输入: n = "1"
输出: "0"
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。
 

提示:

1 <= n.length <= 18
n 只由数字组成
n 不含前导 0
n 代表在 [1, 1018 - 1] 范围内的整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-closest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "stdc++.h"

/*
分别计算出以下每一种可能的方案对应的回文整数，在其中找到与原数最近且不等于原数的数即为答案：
    用原数的前半部分替换后半部分得到的回文整数。
    用原数的前半部分加一后的结果替换后半部分得到的回文整数。
    用原数的前半部分减一后的结果替换后半部分得到的回文整数。
    为防止位数变化导致构造的回文整数错误，因此直接构造 999\dots 999999…999 和 100\dots 001100…001 作为备选答案。
*/
class Solution {
public:
    string nearestPalindromic(string n) {
        long selfNumber = stol(n);
        long res = -1;
        const vector<long>& candidates = getCandidates(n);
        for (auto& candidate : candidates) {
            if (candidate != selfNumber) {
                if (res == -1 ||
                    abs(candidate - selfNumber) < abs(res - selfNumber) ||
                    abs(candidate - selfNumber) == abs(res - selfNumber) && candidate < res)
                {
                    res = candidate;
                }
            }
        }
        return to_string(res);
    }
private:
    vector<long> getCandidates(const string& n) {
        int len = n.length();
        vector<long> candidates = {
            static_cast<long>(pow(10, len - 1)) - 1,
            static_cast<long>(pow(10, len)) + 1,
        };
        long selfPrefix = stol(n.substr(0, (len + 1) / 2));
        for (int i : {selfPrefix - 1, selfPrefix, selfPrefix + 1}) {
            string prefix = to_string(i);
            string candidate = prefix + string(prefix.rbegin() + (len & 1), prefix.rend());
            candidates.push_back(stol(candidate));
        }
        return candidates;
    }
};
